﻿// 402 [CF 17E] Palisection.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <algorithm>

using  namespace std;
/*
http://oj.daimayuan.top/course/22/problem/934

给你一个字符串 s，字符串由小写字母组成，现在你需要求出 s
 中有多少对有公共部分的回文子串，请输出答案 mod 51123987。

输入格式
第一行一个整数 n 表示字符串的长度。
第二行一个字符串 s。

输出格式
输出一个整数表示答案 mod 51123987。

样例输入
4
babb
样例输出
6
数据规模
对于所有数据，保证 1≤n≤2×106， 字符串均由小写字母构成。
*/


int n, m, p[4000002], f[2000002], v[2000002];
char s[2000002], t[4000003];
const int mod = 51123987;

void manacher() {
	//n = strlen(s + 1);
	m = 0;
	t[++m] = '$';
	for (int i = 1; i <= n; i++) {
		t[++m] = s[i]; t[++m] = '$';
	}
	int M = 0, R = 0;
	for (int i = 1; i <= m; i++) {
		if (i > R)
			p[i] = 1;
		else
			p[i] = min(p[2 * M - i], R - i + 1);
		while (i - p[i] > 0 && i + p[i] <= m && t[i - p[i]] == t[i+p[i]])
			++p[i];
		if (i + p[i] - 1 > R)
			M = i, R = i + p[i] - 1;
	}
	long long x = 0;
	for (int i = 1; i <= m; i++) {
		int l = (i-p[i]+2)/2, r = i / 2;
		++v[l]; --v[r+1];
		l = (i + 1) / 2; r = (i + p[i] - 2)/2;
		++f[l]; --f[r + 1];
		x += r - l + 1;
	}

	for (int i = 1; i <= n+1; i++) {
		v[i] += v[i - 1];
	}
	for (int i = 1; i <= n; i++)
		f[i] += f[i - 1];
	for (int i = n - 1; i; --i) 
		v[i] += v[i + 1], v[i] %= mod;

	long long ans = 0;
	if (x & 1)
		ans = x % mod * ((x - 1) / 2 % mod) % mod;
	else
		ans = x / 2 % mod * ((x - 1) % mod) % mod;

	for (int i = 1; i <= n; i++) {
		ans -= 1LL*f[i] * v[i + 1] % mod;
		if (ans < 0)
			ans += mod;
	}

	printf("%lld\n",ans);

}

int main()
{
	scanf("%d%s",&n,s+1);
	manacher();

	return 0;
}

 